package airthmetic.exercise.backtrack;

import java.util.*;

public class _77_组合 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Deque<Integer> queue = new LinkedList();
        backtrack(n,k,1,queue,res);
        return res;
    }

    public void backtrack(int n, int k, int start, Deque<Integer> queue, List<List<Integer>> res){
        if(queue.size() == k){
            res.add(new ArrayList<Integer>(queue));
            return;
        }

        for(int i=start; i<=n; i++){
            queue.addLast(i);
            backtrack(n,k,i+1,queue,res);
            queue.removeLast();
        }
    }
}
